{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Substring with At Least K Repeating Characters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #divide-and-conquer #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #分治 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestSubstring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #至少有 K 个重复字符的最长子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> 和一个整数 <code>k</code> ，请你找出 <code>s</code> 中的最长子串，&nbsp;要求该子串中的每一字符出现次数都不少于 <code>k</code> 。返回这一子串的长度。</p>\n",
    "\n",
    "<p data-pm-slice=\"1 1 []\">如果不存在这样的子字符串，则返回 0。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aaabb\", k = 3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>最长子串为 \"aaa\" ，其中 'a' 重复了 3 次。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"ababbc\", k = 2\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>最长子串为 \"ababb\" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>s</code> 仅由小写英文字母组成</li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-substring-with-at-least-k-repeating-characters](https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-substring-with-at-least-k-repeating-characters](https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aaabb\"\\n3', '\"ababbc\"\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def longestSubstring(self, s, k):\n",
    "        if len(s) < k:\n",
    "            return 0\n",
    "        for c in set(s):\n",
    "            if s.count(c) < k:\n",
    "                return max(self.longestSubstring(t, k) for t in s.split(c))\n",
    "        return len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "\n",
    "\n",
    "        def dfs(s, l, r, k):\n",
    "            cnt = collections.Counter(s[l:r + 1])\n",
    "            split = None\n",
    "            for c in cnt:\n",
    "                if 0 < cnt[c] < k:\n",
    "                    split = c\n",
    "                    break\n",
    "            if not split:\n",
    "                return r - l + 1\n",
    "            i = l\n",
    "            res = 0\n",
    "            while i <= r:\n",
    "\n",
    "                while i <= r and s[i] == split:\n",
    "\n",
    "                    i += 1\n",
    "                if i > r:\n",
    "                    break\n",
    "                start = i\n",
    "                while i <= r and s[i] != split:\n",
    "                    i += 1\n",
    "                \n",
    "                length = dfs(s, start, i - 1, k)\n",
    "                res = max(res, length)\n",
    "            return res\n",
    "\n",
    "        n = len(s)\n",
    "        return dfs(s, 0, n - 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        # 分治法\n",
    "        maximum=-1\n",
    "        alpha_set=set(s)\n",
    "        for alpha in alpha_set:\n",
    "            if s.count(alpha)<k:\n",
    "                longest=max([self.longestSubstring(s_sub, k) for s_sub in s.split(alpha)])\n",
    "                maximum=max(maximum,longest)\n",
    "        return maximum if maximum>=0 else len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        from collections import defaultdict\n",
    "        dict = defaultdict(int)\n",
    "        for c in s:\n",
    "            dict[c]+=1\n",
    "        split = []\n",
    "        pre = 0 \n",
    "        for i,c in enumerate(s):\n",
    "            if dict[c]<k:\n",
    "                split.append([pre,i-1])\n",
    "                pre = i+1\n",
    "        if not split:\n",
    "            return len(s)\n",
    "        split.append([pre,len(s)-1])\n",
    "        maxL = 0\n",
    "        for item in split:\n",
    "            l,r = item[0],item[1]\n",
    "            if l<=r:\n",
    "                maxL = max(maxL,self.longestSubstring(s[l:r+1],k))\n",
    "        return maxL"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 方法二、前缀和+分治（后序遍历）\n",
    "# 时间复杂度：构造前缀和数组需要 O(N), \n",
    "# 分治划分区间进行 O(logN) 次（即递归树高度 2^h =），\n",
    "# 每轮需要 O(N) 时间验证区间 [start,end] \n",
    "# 合法性，因此总的时间复杂度为 O(NlogN)。\n",
    "\n",
    "# 空间复杂度：O(N)，对于每个起点都要申请 26 字符大小数组（比 hash 表快）\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        # 1. 计算前缀和\n",
    "        prefix = [[0] * (n + 1) for _ in range(26)]\n",
    "        for i in range(n):\n",
    "            for j in range(26):\n",
    "                prefix[j][i+1] = prefix[j][i]  # 把前一个抄过来先\n",
    "            prefix[ord(s[i])-97][i+1] += 1  # 注意下标\n",
    "        # 2. 用栈实现后序遍历（因为本题答案是全局，因此可以迭代实现）\n",
    "        stack, res = [(0, n - 1)], 0\n",
    "        while stack:  # 枚举区间不存在则结束\n",
    "            start, end = stack.pop()\n",
    "            for i in range(start, end + 1):\n",
    "                if prefix[ord(s[i])-97][end+1] - prefix[ord(s[i])-97][start] < k:\n",
    "                    stack.extend([(start, i - 1), (i + 1, end)])\n",
    "                    break\n",
    "            else:  # 如果没有 break 则证明 [start, end] 区间满足条件则更新\n",
    "                res = max(res, end - start + 1)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        res = []\n",
    "        tmp = [0] * 26\n",
    "        res.append(tmp[:])\n",
    "        for ch in s:\n",
    "            tmp[ord(ch) - ord('a')] += 1\n",
    "            res.append(tmp[::])\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(i, j):\n",
    "            nonlocal ans\n",
    "            if i > j or j - i + 1 < max(k, ans):\n",
    "                return            \n",
    "            tmp = [res[j + 1][kk] - res[i][kk] for kk in range(26)]\n",
    "            banned = set()\n",
    "            for l in range(26):\n",
    "                if tmp[l] and tmp[l] < k:\n",
    "                    banned.add(l)\n",
    "            if not banned:\n",
    "                ans = max(ans, j - i + 1)\n",
    "                return\n",
    "            stack = []\n",
    "            for p in range(i, j + 1):\n",
    "                if ord(s[p]) - ord('a') in banned:\n",
    "                    if stack:\n",
    "                        dfs(stack[0], stack[-1])\n",
    "                        stack = []\n",
    "                else:\n",
    "                    stack.append(p)\n",
    "            if stack:\n",
    "                dfs(stack[0], stack[-1])\n",
    "\n",
    "        dfs(0, n - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        l1 = [[0] * (n + 1) for _ in range(26)]\n",
    "        for i in range(n):\n",
    "            for j in range(26):\n",
    "                l1[j][i+1] = l1[j][i]  \n",
    "            l1[ord(s[i])-97][i+1] += 1  \n",
    "        stack, res = [(0, n - 1)], 0\n",
    "        while stack:  \n",
    "            start, end = stack.pop()\n",
    "            for i in range(start, end + 1):\n",
    "                if l1[ord(s[i])-97][end+1] - l1[ord(s[i])-97][start] < k:\n",
    "                    stack.extend([(start, i - 1), (i + 1, end)])\n",
    "                    break\n",
    "            else: \n",
    "                res = max(res, end - start + 1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        if len(s) < k:\n",
    "            return 0\n",
    "        stat = defaultdict(list)\n",
    "        for i, ch in enumerate(s):\n",
    "            stat[ch].append(i)\n",
    "\n",
    "        for ch, poses in stat.items():\n",
    "            if len(poses) < k:\n",
    "                starts, ends = [-1] + poses, poses + [len(s)]\n",
    "                return max([self.longestSubstring(s[start + 1: end], k) for start, end in zip(starts, ends)])\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        dic = dict()\n",
    "        t = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in dic:\n",
    "                dic[s[i]] = t\n",
    "                t+=1\n",
    "        a = [[0]*t for _ in range(len(s))]\n",
    "        if k==1:\n",
    "            max_l = 1\n",
    "        else:\n",
    "            max_l = 0\n",
    "        b = [0]*len(s)\n",
    "        for i in range(len(s)):\n",
    "            a[i][dic[s[i]]]+=1\n",
    "            b[i] = dic[s[i]]\n",
    "        for j in range(1,len(s)):\n",
    "            for i in range(len(s)-j):\n",
    "                a[i][dic[s[i+j]]]+=1\n",
    "                if a[i][b[i]]<k:\n",
    "                    continue\n",
    "                if max_l != (j+1):\n",
    "                    flag = True\n",
    "                    for m in range(len(a[i])):\n",
    "                        if a[i][m]!=0 and a[i][m]<k:\n",
    "                            flag = False\n",
    "                            if a[i][m]<a[i][b[i]]:\n",
    "                                b[i] = m\n",
    "                    if flag:\n",
    "                        max_l = (j+1)\n",
    "        return max_l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        dic = dict()\n",
    "        t = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in dic:\n",
    "                dic[s[i]] = t\n",
    "                t+=1\n",
    "        a = [[0]*t for _ in range(len(s))]\n",
    "        if k==1:\n",
    "            max_l = 1\n",
    "        else:\n",
    "            max_l = 0\n",
    "        b = [0]*len(s)\n",
    "        for i in range(len(s)):\n",
    "            a[i][dic[s[i]]]+=1\n",
    "            b[i] = dic[s[i]]\n",
    "        for j in range(1,len(s)):\n",
    "            for i in range(len(s)-j):\n",
    "                a[i][dic[s[i+j]]]+=1\n",
    "                if a[i][b[i]]<k:\n",
    "                    continue\n",
    "                if max_l != (j+1):\n",
    "                    flag = True\n",
    "                    for m in range(len(a[i])):\n",
    "                        if a[i][m]!=0 and a[i][m]<k:\n",
    "                            flag = False\n",
    "                            if a[i][m]<a[i][b[i]]:\n",
    "                                b[i] = m\n",
    "                    if flag:\n",
    "                        max_l = (j+1)\n",
    "        return max_l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        def dfs(data, k, left, right, retlist):\n",
    "            if right - left + 1 < k:\n",
    "                return\n",
    "            leftIdx, rightIdx = left, right\n",
    "            dcmap = defaultdict(list)\n",
    "            idx = -1\n",
    "            for i in range(leftIdx, rightIdx + 1):\n",
    "                dcmap[data[i]].append(i)\n",
    "            for val in dcmap.values():\n",
    "                if len(val) < k:\n",
    "                    idx = val[0]\n",
    "            # print(left, right, idx, retlist,dcmap)\n",
    "            if idx > -1:\n",
    "                dfs(data, k, left, idx - 1, retlist)\n",
    "                dfs(data, k, idx + 1, right, retlist)\n",
    "            else:\n",
    "                retlist.append(data[left : right + 1])\n",
    "        \n",
    "        ret = []\n",
    "        maxlen = 0\n",
    "        dfs(s, k, 0, len(s) - 1, ret)\n",
    "        if ret:\n",
    "            ret.sort(key = lambda x : len(x), reverse = True)\n",
    "            maxlen = len(ret[0])\n",
    "            # print(ret)\n",
    "        return maxlen\n",
    "\n",
    "\n",
    "        def longestSubstring1(s, k):\n",
    "            n = len(s)\n",
    "            maxStr = ''\n",
    "            subStr = ''\n",
    "            dcmap = defaultdict(list)\n",
    "            ids = []\n",
    "            subStrDc = defaultdict(int)\n",
    "            isOk = False\n",
    "            for i in range(n):\n",
    "                dcmap[s[i]].append(i)\n",
    "            for key, val in dcmap.items():\n",
    "                if len(val) < k:\n",
    "                    ids.extend(val)\n",
    "            m = len(ids)\n",
    "            print('ids', ids)\n",
    "            if not ids:\n",
    "                return len(s)\n",
    "            for i in range(m):\n",
    "                if i == 0:\n",
    "                    subStr = s[:ids[i]]\n",
    "                elif i == m - 1:\n",
    "                    subStr = s[ids[i] :]\n",
    "                else:\n",
    "                    subStr = s[ids[i - 1] : ids[i]] \n",
    "                print('i=', i, subStr, maxStr)\n",
    "                if len(subStr) > len(maxStr):\n",
    "                    subStrDc.clear()\n",
    "                    isOk = True\n",
    "                    for temStr in subStr:\n",
    "                        subStrDc[temStr] += 1\n",
    "                    for val in subStrDc.values():\n",
    "                        if val < k:\n",
    "                            isOk = False\n",
    "                    if isOk:\n",
    "                        maxStr = subStr\n",
    "            return len(maxStr)\n",
    "\n",
    "        # return longestSubstring1(s, k)\n",
    "\n",
    "        def longestSubstring2(s, k):\n",
    "            n = len(s)\n",
    "            dp, maxlst = [], [0]\n",
    "            lst = [0] * 26\n",
    "            lst[ord(s[0]) - ord('a')] = 1\n",
    "            dp.append(lst)\n",
    "            # if k <= 1:\n",
    "            #     maxlst[0] = 1\n",
    "\n",
    "            for i in range(1, n):\n",
    "                temlst = dp[i - 1][:]\n",
    "                temlst[ord(s[i]) - ord('a')] += 1\n",
    "                dp.append(temlst)\n",
    "\n",
    "        # return longestSubstring2(s, k)\n",
    "\n",
    "        # def backStack(data, )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        def dfs(data, k, left, right, retlist):\n",
    "            \n",
    "            if right - left + 1 < k:\n",
    "                return\n",
    "            leftIdx, rightIdx = left, right\n",
    "            dcmap = defaultdict(list)\n",
    "            idx = -1\n",
    "            for i in range(leftIdx, rightIdx + 1):\n",
    "                dcmap[data[i]].append(i)\n",
    "            for val in dcmap.values():\n",
    "                if len(val) < k:\n",
    "                    idx = val[0]\n",
    "            print(left, right, idx, retlist,dcmap)\n",
    "            if idx > -1:\n",
    "                dfs(data, k, left, idx - 1, retlist)\n",
    "                dfs(data, k, idx + 1, right, retlist)\n",
    "            else:\n",
    "                retlist.append(data[left : right + 1])\n",
    "        \n",
    "        ret = []\n",
    "        maxlen = 0\n",
    "        dfs(s, k, 0, len(s) - 1, ret)\n",
    "        if ret:\n",
    "            ret.sort(key = lambda x : len(x), reverse = True)\n",
    "            maxlen = len(ret[0])\n",
    "            print(ret)\n",
    "        return maxlen\n",
    "\n",
    "\n",
    "        def longestSubstring1(s, k):\n",
    "            n = len(s)\n",
    "            maxStr = ''\n",
    "            subStr = ''\n",
    "            dcmap = defaultdict(list)\n",
    "            ids = []\n",
    "            subStrDc = defaultdict(int)\n",
    "            isOk = False\n",
    "            for i in range(n):\n",
    "                dcmap[s[i]].append(i)\n",
    "            for key, val in dcmap.items():\n",
    "                if len(val) < k:\n",
    "                    ids.extend(val)\n",
    "            m = len(ids)\n",
    "            print('ids', ids)\n",
    "            if not ids:\n",
    "                return len(s)\n",
    "            for i in range(m):\n",
    "                if i == 0:\n",
    "                    subStr = s[:ids[i]]\n",
    "                elif i == m - 1:\n",
    "                    subStr = s[ids[i] :]\n",
    "                else:\n",
    "                    subStr = s[ids[i - 1] : ids[i]] \n",
    "                print('i=', i, subStr, maxStr)\n",
    "                if len(subStr) > len(maxStr):\n",
    "                    subStrDc.clear()\n",
    "                    isOk = True\n",
    "                    for temStr in subStr:\n",
    "                        subStrDc[temStr] += 1\n",
    "                    for val in subStrDc.values():\n",
    "                        if val < k:\n",
    "                            isOk = False\n",
    "                    if isOk:\n",
    "                        maxStr = subStr\n",
    "            return len(maxStr)\n",
    "\n",
    "        # return longestSubstring1(s, k)\n",
    "\n",
    "        def longestSubstring2(s, k):\n",
    "            n = len(s)\n",
    "            dp, maxlst = [], [0]\n",
    "            lst = [0] * 26\n",
    "            lst[ord(s[0]) - ord('a')] = 1\n",
    "            dp.append(lst)\n",
    "            # if k <= 1:\n",
    "            #     maxlst[0] = 1\n",
    "\n",
    "            for i in range(1, n):\n",
    "                temlst = dp[i - 1][:]\n",
    "                temlst[ord(s[i]) - ord('a')] += 1\n",
    "                dp.append(temlst)\n",
    "\n",
    "        # return longestSubstring2(s, k)\n",
    "\n",
    "        # def backStack(data, )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        a = ord('a')\n",
    "        def dfs(l, r):\n",
    "            if l > r:\n",
    "                return 0\n",
    "            cnt = [0] * 26\n",
    "            for i in range(l, r + 1):\n",
    "                cnt[ord(s[i]) - a] += 1\n",
    "            lb = rb = -1\n",
    "            for i in range(l, r + 1):\n",
    "                if cnt[ord(s[i]) - a] < k:\n",
    "                    lb = i\n",
    "                    break\n",
    "            for i in range(r, l - 1, -1):\n",
    "                if cnt[ord(s[i]) - a] < k:\n",
    "                    rb = i\n",
    "                    break\n",
    "            if lb == rb == -1:\n",
    "                return r - l + 1\n",
    "            else:\n",
    "                return max(dfs(l, lb - 1), dfs(rb + 1, r), dfs(lb + 1, rb - 1))\n",
    "        return dfs(0, len(s) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        def dfs(data, k, left, right, retlist):\n",
    "            \n",
    "            if right - left + 1 < k:\n",
    "                return\n",
    "            leftIdx, rightIdx = left, right\n",
    "            dcmap = defaultdict(list)\n",
    "            idx = -1\n",
    "            # for i in range(leftIdx, rightIdx):\n",
    "            #     dcmap[data[i]].append(i)\n",
    "            while rightIdx >= leftIdx:\n",
    "                dcmap[data[leftIdx]].append(leftIdx)\n",
    "                leftIdx += 1\n",
    "                if rightIdx >= leftIdx:\n",
    "                    dcmap[data[rightIdx]].append(rightIdx)\n",
    "                    rightIdx -= 1\n",
    "\n",
    "            # print(dcmap)\n",
    "            for val in dcmap.values():\n",
    "                if len(val) < k:\n",
    "                    idx = val[0]\n",
    "            print(left, right, idx, retlist,dcmap)\n",
    "            if idx > -1:\n",
    "                dfs(data, k, left, idx - 1, retlist)\n",
    "                dfs(data, k, idx + 1, right, retlist)\n",
    "            else:\n",
    "                retlist.append(data[left : right + 1])\n",
    "        \n",
    "        ret = []\n",
    "        maxlen = 0\n",
    "        dfs(s, k, 0, len(s) - 1, ret)\n",
    "        if ret:\n",
    "            ret.sort(key = lambda x : len(x), reverse = True)\n",
    "            maxlen = len(ret[0])\n",
    "            print(ret)\n",
    "        return maxlen\n",
    "\n",
    "\n",
    "        def longestSubstring1(s, k):\n",
    "            n = len(s)\n",
    "            maxStr = ''\n",
    "            subStr = ''\n",
    "            dcmap = defaultdict(list)\n",
    "            ids = []\n",
    "            subStrDc = defaultdict(int)\n",
    "            isOk = False\n",
    "            for i in range(n):\n",
    "                dcmap[s[i]].append(i)\n",
    "            for key, val in dcmap.items():\n",
    "                if len(val) < k:\n",
    "                    ids.extend(val)\n",
    "            m = len(ids)\n",
    "            print('ids', ids)\n",
    "            if not ids:\n",
    "                return len(s)\n",
    "            for i in range(m):\n",
    "                if i == 0:\n",
    "                    subStr = s[:ids[i]]\n",
    "                elif i == m - 1:\n",
    "                    subStr = s[ids[i] :]\n",
    "                else:\n",
    "                    subStr = s[ids[i - 1] : ids[i]] \n",
    "                print('i=', i, subStr, maxStr)\n",
    "                if len(subStr) > len(maxStr):\n",
    "                    subStrDc.clear()\n",
    "                    isOk = True\n",
    "                    for temStr in subStr:\n",
    "                        subStrDc[temStr] += 1\n",
    "                    for val in subStrDc.values():\n",
    "                        if val < k:\n",
    "                            isOk = False\n",
    "                    if isOk:\n",
    "                        maxStr = subStr\n",
    "            return len(maxStr)\n",
    "\n",
    "        # return longestSubstring1(s, k)\n",
    "\n",
    "        def longestSubstring2(s, k):\n",
    "            n = len(s)\n",
    "            dp, maxlst = [], [0]\n",
    "            lst = [0] * 26\n",
    "            lst[ord(s[0]) - ord('a')] = 1\n",
    "            dp.append(lst)\n",
    "            # if k <= 1:\n",
    "            #     maxlst[0] = 1\n",
    "\n",
    "            for i in range(1, n):\n",
    "                temlst = dp[i - 1][:]\n",
    "                temlst[ord(s[i]) - ord('a')] += 1\n",
    "                dp.append(temlst)\n",
    "\n",
    "        # return longestSubstring2(s, k)\n",
    "\n",
    "        # def backStack(data, )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "\n",
    "        def find(s,k):\n",
    "            if len(s) == 0:\n",
    "                return 0\n",
    "            flag = False\n",
    "\n",
    "            char_count = defaultdict(int)\n",
    "            char_index = defaultdict(list)\n",
    "            for i,ch in enumerate(s):\n",
    "                char_count[ch] += 1\n",
    "                char_index[ch].append(i)\n",
    "\n",
    "            for ch in char_count:\n",
    "                if char_count[ch] < k:\n",
    "                    flag = True\n",
    "                    invalid = ch\n",
    "                    char_count.pop(ch)\n",
    "                    break\n",
    "            if not flag:\n",
    "                return len(s)\n",
    "            else:\n",
    "                if len(char_index[invalid]) == 1:\n",
    "                    invalid_start = char_index[invalid][0]\n",
    "                    return max(find(s[:invalid_start], k),find(s[invalid_start+1:], k))\n",
    "                else:\n",
    "                    ans = 0\n",
    "                    invalid_start = -1\n",
    "                    for idx in char_index[invalid]:\n",
    "                        ans = max(ans, find(s[invalid_start+1:idx], k))\n",
    "                        invalid_start = idx\n",
    "                    ans = max(ans, find(s[char_index[invalid][-1]:],k))\n",
    "                    return ans\n",
    "\n",
    "        if len(s) < k:\n",
    "            return 0\n",
    "        return find(s,k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, s:str, left: int, right: int, k: int) -> int:\n",
    "        res = 0\n",
    "        split = -1\n",
    "        for i in range(left, right):\n",
    "            if s[left:right].count(s[i]) < k:\n",
    "                split = i\n",
    "                break\n",
    "        if split == -1:\n",
    "            return right - left\n",
    "        while left < right:\n",
    "            while left < right and left == split:\n",
    "                left += 1\n",
    "            if left >= right:\n",
    "                break\n",
    "            start = left\n",
    "            while left < right and left != split:\n",
    "                left += 1\n",
    "            res = max(res, self.dfs(s, start, left, k))\n",
    "        return res\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        return self.dfs(s, 0, len(s), k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.mxl = 0\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        d = {}\n",
    "        for i in s:\n",
    "            if i not in d:\n",
    "                d[i] = 0\n",
    "            d[i] += 1\n",
    "        mxl = 0\n",
    "        def dfs(st,ed,k):\n",
    "            if st >= ed:\n",
    "                return \n",
    "            low = st\n",
    "            while low < ed:\n",
    "                if d[s[low]] >= k:\n",
    "                    low += 1\n",
    "                else:\n",
    "                    break\n",
    "            newd = {}\n",
    "            for i in s[st:low]:\n",
    "                if i not in newd:\n",
    "                    newd[i] = 0\n",
    "                newd[i] += 1\n",
    "            pos = st\n",
    "            flag = 0\n",
    "            for i in range(st,low):\n",
    "                if newd[s[i]] < k:\n",
    "                    flag = 1\n",
    "                    if i - pos >= k:\n",
    "                        dfs(pos,i,k)\n",
    "                    pos = i+1\n",
    "            if flag == 1 and low - pos >= k:\n",
    "                dfs(pos,low,k)\n",
    "            l = low-pos\n",
    "            if flag == 0 and l > self.mxl and l >= k:\n",
    "                self.mxl = l\n",
    "            dfs(low+1,ed,k)\n",
    "        dfs(0,len(s),k)\n",
    "        return self.mxl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    allChar = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "    def rec_longestSubstring(self, s, s_idx, e_idx, length, k):\n",
    "        curr_len = e_idx - s_idx\n",
    "        if length >= curr_len:\n",
    "            return length\n",
    "        invalid_lst = list()\n",
    "        for c in Solution.allChar:\n",
    "            if 0 < self.cnt_lst[e_idx][c] - self.cnt_lst[s_idx][c] < k:\n",
    "                invalid_lst.append(c)\n",
    "        if len(invalid_lst) == 0:\n",
    "            return curr_len\n",
    "        \n",
    "        rec_s_idx = cursor = 0\n",
    "        while cursor < curr_len:\n",
    "            if s[cursor] in invalid_lst:\n",
    "                length = self.rec_longestSubstring(s[rec_s_idx: cursor], s_idx + rec_s_idx, s_idx + cursor, length, k)\n",
    "                rec_s_idx = cursor + 1\n",
    "            if cursor == curr_len-1:\n",
    "                length = self.rec_longestSubstring(s[rec_s_idx:], s_idx + rec_s_idx, s_idx + cursor+1, length, k)\n",
    "            cursor += 1\n",
    "        return length\n",
    "\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        if len(s) < k:\n",
    "            return 0\n",
    "        if k == 1:\n",
    "            return len(s)\n",
    "\n",
    "        res = 0\n",
    "        cnt_dict, self.cnt_lst = dict(), list()\n",
    "        for c in Solution.allChar:\n",
    "            cnt_dict.update({c: 0})\n",
    "        self.cnt_lst.append(cnt_dict)        \n",
    "        for s_c in s:\n",
    "            curr_dict = self.cnt_lst[-1].copy()\n",
    "            curr_dict[s_c] += 1\n",
    "            self.cnt_lst.append(curr_dict)\n",
    "        \n",
    "        return self.rec_longestSubstring(s, 0, len(s), res, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.mxl = 0\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        d = {}\n",
    "        for i in s:\n",
    "            if i not in d:\n",
    "                d[i] = 0\n",
    "            d[i] += 1\n",
    "        mxl = 0\n",
    "        def dfs(st,ed,k):\n",
    "            if st >= ed:\n",
    "                return \n",
    "            low = st\n",
    "            while low < ed:\n",
    "                if d[s[low]] >= k:\n",
    "                    low += 1\n",
    "                else:\n",
    "                    break\n",
    "            newd = {}\n",
    "            for i in s[st:low]:\n",
    "                if i not in newd:\n",
    "                    newd[i] = 0\n",
    "                newd[i] += 1\n",
    "            pos = st\n",
    "            flag = 0\n",
    "            for i in range(st,low):\n",
    "                if newd[s[i]] < k:\n",
    "                    flag = 1\n",
    "                    if i - pos >= k:\n",
    "                        dfs(pos,i,k)\n",
    "                    pos = i+1\n",
    "            if flag == 1 and low - pos >= k:\n",
    "                dfs(pos,low,k)\n",
    "            l = low-pos\n",
    "            if flag == 0 and l > self.mxl and l >= k:\n",
    "                self.mxl = l\n",
    "            dfs(low+1,ed,k)\n",
    "        dfs(0,len(s),k)\n",
    "        return self.mxl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        sets = set(list(s))\n",
    "        d = {}\n",
    "        for i, c in enumerate(s):\n",
    "            for key in d:\n",
    "                d[key][i + 1] = d[key][i]\n",
    "            if c not in d:\n",
    "                d[c] = [0] * (len(s) + 1)\n",
    "            d[c][i + 1] = d[c][i + 1] + 1\n",
    "        \n",
    "        def divide(a, b):\n",
    "            if b < a:\n",
    "                return 0\n",
    "            for i in range(a, b + 1):\n",
    "                if d[s[i]][b + 1] - d[s[i]][a] < k:\n",
    "                    return max(divide(a, i - 1), divide(i + 1, b))\n",
    "            else:\n",
    "                return b - a + 1\n",
    "        \n",
    "        return divide(0, len(s) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        prefix_sum = [[0] * (len(s) + 1) for _ in range(26)]\n",
    "        for i in range(len(s)):\n",
    "            for j in range(26):\n",
    "                prefix_sum[j][i + 1] = prefix_sum[j][i]\n",
    "            prefix_sum[ord(s[i]) - ord(\"a\")][i + 1] += 1\n",
    "        # prefix_sum_dict = collections.defaultdict(list)\n",
    "        # for i in range(len(s)):\n",
    "        #     prefix_sum_dict[s[i]]\n",
    "        result = 0\n",
    "        def dfs(left, right):\n",
    "            nonlocal result\n",
    "            for i in range(left, right + 1):\n",
    "                idx = ord(s[i]) - ord(\"a\")\n",
    "                if prefix_sum[idx][right + 1] - prefix_sum[idx][left] < k:\n",
    "                    return max(dfs(left, i - 1), dfs(i + 1, right))\n",
    "            result = max(right - left + 1, result)\n",
    "            return right - left + 1\n",
    "        \n",
    "        return dfs(0, len(s) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        '''temp_d={}\n",
    "        d=[]\n",
    "        for i in range(len(s)):\n",
    "            temp_d[s[i]]=temp_d.get(s[i],0)+1\n",
    "        for key in temp_d:\n",
    "            if temp_d[key]>=k:\n",
    "                d.append(key)\n",
    "        res=[0]*len(s)#以i结尾的最长字串的长度\n",
    "        for i in range(len(s)):\n",
    "            if i==0 and s[i] in d:\n",
    "                res[0]=1\n",
    "            else:\n",
    "                if s[i] in d:\n",
    "                    res[i]=res[i-1]+1\n",
    "                else:\n",
    "                    res[i]=0\n",
    "        return max(res)'''#wrong 审题！ 没那么简单\n",
    "        #初始化\n",
    "        n=len(s)\n",
    "        #prefix=[[0]*(n+1)]*26# 26 al\n",
    "        prefix=[[0]*(n+1) for i in range(26)]#!结果不同！\n",
    "        for i in range(n):\n",
    "            for j in range(26):\n",
    "                prefix[j][i+1]=prefix[j][i]\n",
    "            prefix[ord(s[i])-ord('a')][i+1]+=1\n",
    "            #print(ord(s[i])-ord('a'),'000')\n",
    "            #print('222',prefix)\n",
    "        def divider(start,end):\n",
    "            for i in range(start,end+1):\n",
    "                if prefix[ord(s[i])-ord('a')][end+1]-prefix[ord(s[i])-ord('a')][start]<k:\n",
    "                    return max(divider(start,i-1),divider(i+1,end))\n",
    "            return max(end-start+1,0)\n",
    "\n",
    "        return divider(0,n-1)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        \n",
    "        prefix = [[0] * (n + 1) for _ in range(26)]\n",
    "        for i in range(n):\n",
    "            for j in range(26):\n",
    "                prefix[j][i+1] = prefix[j][i]  # 把前一个抄过来先\n",
    "            prefix[ord(s[i])-97][i+1] += 1  # 注意下标\n",
    "        \n",
    "        def helper(start, end):\n",
    "            for i in range(start, end+1):\n",
    "                if prefix[ord(s[i])-ord('a')][end+1] - prefix[ord(s[i])-ord('a')][start] < k:\n",
    "                    return max(helper(start, i-1), helper(i+1, end))\n",
    "            return max(0, end-start+1)\n",
    "        \n",
    "        return helper(0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        import copy\n",
    "        prefix = [[0] * 26 for _ in range(n+1)]\n",
    "        for i in range(n):\n",
    "            prefix[i+1] = copy.copy(prefix[i])  # 把前一个抄过来先\n",
    "            prefix[i+1][ord(s[i])-97] += 1  # 注意下标\n",
    "\n",
    "        def helper(start, end):\n",
    "            for i in range(start, end+1):\n",
    "                if prefix[end+1][ord(s[i])-ord('a')] - prefix[start][ord(s[i])-ord('a')] < k:\n",
    "                    return max(helper(start, i-1), helper(i+1, end))\n",
    "            return max(0, end-start+1)\n",
    "        \n",
    "        return helper(0, n-1)\n",
    "# https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/solutions/507404/26zi-fu-qian-zhui-he-fen-zhi-er-cha-shu-de-hou-xu-/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        return self.dfs(s, 0, len(s), k)\n",
    "\n",
    "    def dfs(self, s, start, end, k):\n",
    "        if end - start < k:\n",
    "            return 0\n",
    "\n",
    "        nums = [0] * 26\n",
    "        for i in range(start, end):\n",
    "            nums[ord(s[i]) - ord('a')] += 1\n",
    "        for i in range(start, end):\n",
    "            if nums[ord(s[i]) - ord('a')] < k:\n",
    "                return max(self.dfs(s, start, i, k),\n",
    "                           self.dfs(s, i+1, end, k))\n",
    "        return end - start"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        a = ord('a')\n",
    "        def dfs(l, r):\n",
    "            if l > r:\n",
    "                return 0\n",
    "            cnt = [0] * 26\n",
    "            for i in range(l, r + 1):\n",
    "                cnt[ord(s[i]) - a] += 1\n",
    "            idx = -1\n",
    "            for i in range(l, r + 1):\n",
    "                if cnt[ord(s[i]) - a] < k:\n",
    "                    idx = i\n",
    "                    break\n",
    "            if idx == -1:\n",
    "                return r - l + 1\n",
    "            else:\n",
    "                return max(dfs(l, idx - 1), dfs(idx + 1, r))\n",
    "        return dfs(0, len(s) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        ALL_CHAR = 26\n",
    "        def sub_str(left: int, right: int):\n",
    "            char_num = [0] * ALL_CHAR\n",
    "            for i in range(left, right):\n",
    "                char_num[ord(s[i]) - ord('a')] += 1\n",
    "            split = ''\n",
    "            for i in range(ALL_CHAR):\n",
    "                if 0 < char_num[i] < k:\n",
    "                    split = chr(ord('a') + i)\n",
    "                    break\n",
    "            if split == '':\n",
    "                return right - left\n",
    "            else:\n",
    "                for i in range(left, right):\n",
    "                    if s[i] == split:\n",
    "                        break\n",
    "\n",
    "                left_num = sub_str(left, i)\n",
    "                right_num = sub_str(i+1, right)\n",
    "                # print(left_num)\n",
    "                # print(right_num)\n",
    "                return max(left_num, right_num)\n",
    "\n",
    "        return sub_str(0, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        def dfs(s, left, right, k):\n",
    "            if left > right:\n",
    "                return 0\n",
    "            # 统计每个字符出现的次数\n",
    "            cnt = [0] * 26\n",
    "            for i in range(left, right + 1):\n",
    "                cnt[ord(s[i]) - ord('a')] += 1\n",
    "\n",
    "            # 找到第一个不满足条件的字符\n",
    "            split = 0\n",
    "            for i in range(26):\n",
    "                if 0 < cnt[i] < k:\n",
    "                    split = chr(i + ord(\"a\"))\n",
    "                    break\n",
    "            if split == 0:\n",
    "                return right - left + 1\n",
    "\n",
    "            point = left\n",
    "            for i in range(left, right + 1):\n",
    "                if s[i] == split:\n",
    "                    point = i\n",
    "                    break\n",
    "\n",
    "            return max(dfs(s, left, point - 1, k), dfs(s, point + 1, right, k))\n",
    "\n",
    "        return dfs(s, 0, n - 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        def dfs(left, right):\n",
    "            cnt = [0] * 26\n",
    "            for i in range(left, right + 1):\n",
    "                cnt[ord(s[i]) - ord(\"a\")] += 1\n",
    "\n",
    "            for i in range(left, right + 1):\n",
    "                if cnt[ord(s[i]) - ord(\"a\")] < k:\n",
    "                    return max(dfs(left, i - 1), dfs(i + 1, right))\n",
    "\n",
    "            return right - left + 1\n",
    "\n",
    "        return dfs(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        return self.re(s,k,0,len(s)-1)\n",
    "    def re(self,s,k,start,end):\n",
    "        if end<start:\n",
    "            return 0\n",
    "        seen=[0]*26\n",
    "        for i in range(start,end+1):\n",
    "            seen[ord(s[i])-ord('a')]+=1\n",
    "        for i in range(start,end+1):\n",
    "            if seen[ord(s[i])-ord('a')]<k:\n",
    "                return max(self.re(s,k,start,i-1),self.re(s,k,i+1,end))\n",
    "        return end-start+1\n",
    "        \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#9/5/23 yb\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        if k == 1:\n",
    "            return len(s)\n",
    "\n",
    "        def helper(start, end):\n",
    "            nonlocal k\n",
    "            if end - start < k:\n",
    "                return 0\n",
    "            \n",
    "            ct = [0 for _ in range(26)]\n",
    "\n",
    "            for i in range(start, end):\n",
    "                ct[ord(s[i]) - ord('a')] += 1\n",
    "            \n",
    "            for i in range(26):\n",
    "                if 0 < ct[i] < k:\n",
    "                    for ii in range(start, end):\n",
    "                        if ord(s[ii]) == i + ord('a'):\n",
    "                            left = helper(start, ii)\n",
    "                            right = helper(ii+1, end)\n",
    "                            return max(left, right)\n",
    "            return end - start\n",
    "        return helper(0, len(s))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        count = [0]*26\n",
    "        for c in s:\n",
    "            count[ord(c)-97]+=1\n",
    "        self.max = 0\n",
    "        @cache\n",
    "        def dg(start, end):\n",
    "            if max(count)<k or end-start+1<=self.max:\n",
    "                return 0\n",
    "            for i in range(26):\n",
    "                if count[i]<k and count[i]!=0:\n",
    "                    left = ord(s[start])-97\n",
    "                    right = ord(s[end])-97\n",
    "                    count[left]-=1\n",
    "                    a = dg(start+1, end)\n",
    "                    count[left]+=1\n",
    "                    count[right]-=1\n",
    "                    b = dg(start, end-1)\n",
    "                    count[right]+=1\n",
    "                    self.max = max(self.max, a, b)\n",
    "                    return max(a, b)\n",
    "            self.max = max(self.max, end-start+1)\n",
    "            return end-start+1\n",
    "        return dg(0, len(s)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        def dfs(left,right):\n",
    "            if left > right:\n",
    "                return 0\n",
    "            cntMap = {}\n",
    "            for w in s[left:right+1]:\n",
    "                cntMap[w] = cntMap.get(w, 0) + 1\n",
    "            split = -1\n",
    "            # print(cntMap)\n",
    "            for i in range(left,right+1):     \n",
    "                if cntMap[s[i]] < k:\n",
    "                    split = i\n",
    "                    # print(split, s[i])\n",
    "                    break\n",
    "            if split == -1:\n",
    "                return right-left+1\n",
    "            return max(dfs(left,split-1), dfs(split+1,right))\n",
    "        \n",
    "        return dfs(0,n-1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "\n",
    "        def divid(left, right):\n",
    "            if k>(right-left+1) or (left>right):\n",
    "                return 0\n",
    "            cnt_dict = {}\n",
    "            for i in range(left,right+1):\n",
    "                if s[i] not in cnt_dict:\n",
    "                    cnt_dict[s[i]] = 1\n",
    "                else:\n",
    "                    cnt_dict[s[i]] += 1\n",
    "            min_s = min(cnt_dict, key=cnt_dict.get)\n",
    "            if cnt_dict[min_s]>=k:\n",
    "                return right-left+1\n",
    "            else:\n",
    "                index = s[left:right+1].find(min_s)\n",
    "                return max(divid(left,left+index-1),divid(left+index+1,right))\n",
    "        return divid(0,len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        def partition(left,right):\n",
    "            counter = defaultdict(int)\n",
    "            for i in range(left, right+1):\n",
    "                counter[s[i]] +=1\n",
    "\n",
    "            for mid in range(left, right+1):\n",
    "                if counter[s[mid]] < k:\n",
    "                    return max(partition(left,mid-1), partition(mid+1, right))\n",
    "            return right - left +1\n",
    "        n = len(s)\n",
    "        return partition(0, n-1)\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        import numpy as np \n",
    "\n",
    "        matrix = np.zeros([26, len(s)+1], dtype=np.int32)\n",
    "        index_matrix = np.zeros([26, len(s)+1], dtype=np.int32) - 1\n",
    "        \n",
    "        for i in range(len(s)):\n",
    "            matrix[:, i+1] = matrix[:, i]\n",
    "            matrix[ord(s[i])-ord(\"a\")][i+1] += 1\n",
    "\n",
    "            index_matrix[:, i+1] = index_matrix[:, i]\n",
    "            index_matrix[ord(s[i])-ord(\"a\")][i+1] = i\n",
    "        \n",
    "        def helper(i, j):\n",
    "            if j - i < k:\n",
    "                return 0\n",
    "            x = matrix[:, j] - matrix[:, i]\n",
    "            indices = np.where((x > 0) * (x < k))[0]\n",
    "            if len(indices) == 0:\n",
    "                return j - i\n",
    "            \n",
    "            index = indices[0]\n",
    "            m = int(index_matrix[index][j])\n",
    "            return max(helper(i, m), helper(m+1, j))\n",
    "\n",
    "        return helper(0, len(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        import numpy as np \n",
    "\n",
    "        matrix = np.zeros([26, len(s)+1], dtype=np.int32)\n",
    "        index_matrix = np.zeros([26, len(s)+1], dtype=np.int32) - 1\n",
    "        for i in range(len(s)):\n",
    "            matrix[:, i+1] = matrix[:, i]\n",
    "            matrix[ord(s[i])-ord(\"a\")][i+1] += 1\n",
    "\n",
    "            index_matrix[:, i+1] = index_matrix[:, i]\n",
    "            index_matrix[ord(s[i])-ord(\"a\")][i+1] = i\n",
    "        \n",
    "        # @lru_cache(None)\n",
    "        def helper(i, j):\n",
    "            if j - i < k:\n",
    "                return 0\n",
    "            x = matrix[:, j] - matrix[:, i]\n",
    "            indices = np.where((x > 0) * (x < k))[0]\n",
    "            if len(indices) == 0:\n",
    "                return j - i\n",
    "            \n",
    "            index = indices[0]\n",
    "            m = int(index_matrix[index][j])\n",
    "            return max(helper(i, m), helper(m+1, j))\n",
    "\n",
    "        return helper(0, len(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        # 前缀和+分治法\n",
    "        n = len(s)\n",
    "        if n<k:\n",
    "            return 0\n",
    "        count = [[0]*(n+1) for _ in range(26)]\n",
    "        for i in range(1, n+1):\n",
    "            judge = ord(s[i-1])-ord(\"a\")\n",
    "            for j in range(26):\n",
    "                count[j][i] = count[j][i-1] + (judge==j)\n",
    "        \n",
    "        maxLen = 0\n",
    "        def helper(begin: int, end: int):\n",
    "            if end-begin+1<k:\n",
    "                return 0\n",
    "            subCount = [0] * 26\n",
    "            for i in range(26):\n",
    "                subCount[i] = count[i][end+1] - count[i][begin]\n",
    "\n",
    "            for i in range(begin, end+1):\n",
    "                if subCount[ord(s[i])-ord(\"a\")]<k:\n",
    "                    len_1 = helper(begin, i-1)\n",
    "                    len_2 = helper(i+1, end)\n",
    "                    maxLen = max(len_1, len_2)\n",
    "                    return maxLen\n",
    "            return end - begin + 1\n",
    "        return helper(0, n-1)\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        from collections import Counter\n",
    "        if not s:\n",
    "            return 0\n",
    "\n",
    "        table = Counter(s)\n",
    "        if min(table.values()) >= k:\n",
    "            return len(s)\n",
    "        if max(table.values()) < k:\n",
    "            return 0\n",
    "\n",
    "        i = 0\n",
    "        j = len(s) - 1\n",
    "        if table[s[i]] < k:\n",
    "            i += 1\n",
    "        if table[s[j]] < k:\n",
    "            j -= 1\n",
    "        for x in range(i, j+1):\n",
    "            if table[s[x]] < k:\n",
    "                return max(self.longestSubstring(s[i:x], k), self.longestSubstring(s[x+1:j+1], k))\n",
    "        \n",
    "        return j - i + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j, k):\n",
    "            if j-i+1 < k:\n",
    "                return 0\n",
    "            d = defaultdict(int)\n",
    "            for p in range(i, j+1):\n",
    "                d[s[p]] += 1\n",
    "            res = 0\n",
    "            split = False\n",
    "            for p in range(i, j+1):\n",
    "                if d[s[p]] < k:\n",
    "                    res = max(res, dfs(i, p-1, k), dfs(p+1, j, k))\n",
    "                    split = True\n",
    "                    break\n",
    "            if not split: res = j-i+1\n",
    "            return res\n",
    "\n",
    "        return dfs(0, len(s)-1, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        pre = [[0] * 26 for _ in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(26):\n",
    "                pre[i][j] = pre[i - 1][j] + (chr(97 + j) == s[i - 1])\n",
    "        def foo(a, b):\n",
    "            if a >= b:\n",
    "                return -1\n",
    "            cnt = [pre[b][i] - pre[a][i] for i in range(26)]\n",
    "            ret = flag = -1\n",
    "            for i in range(a, b):\n",
    "                c = ord(s[i]) - 97\n",
    "                if cnt[c] < k:\n",
    "                    if flag == -1:\n",
    "                        flag = a\n",
    "                    ret = max(ret, foo(flag, i))\n",
    "                    flag = i + 1\n",
    "                if flag != -1:\n",
    "                    ret = max(ret, foo(flag, b))\n",
    "                    return ret\n",
    "            return b - a\n",
    "        return max(0, foo(0, n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        pre = [[0] * 26 for _ in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(26):\n",
    "                pre[i][j] = pre[i - 1][j] + (chr(97 + j) == s[i - 1])\n",
    "        def foo(a, b):\n",
    "            if a >= b:\n",
    "                return -1\n",
    "            cnt = [pre[b][i] - pre[a][i] for i in range(26)]\n",
    "            ret = flag = -1\n",
    "            for i in range(a, b):\n",
    "                c = ord(s[i]) - 97\n",
    "                if cnt[c] < k:\n",
    "                    if flag == -1:\n",
    "                        flag = a\n",
    "                    ret = max(ret, foo(flag, i))\n",
    "                    flag = i + 1\n",
    "                if flag != -1:\n",
    "                    ret = max(ret, foo(flag, b))\n",
    "                    return ret\n",
    "            return b - a\n",
    "        return max(0, foo(0, n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from collections import defaultdict\n",
    "    from collections import Counter\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "      \n",
    "        # 边界讨论\n",
    "        if k>n:\n",
    "            return 0\n",
    "        if k ==1 :\n",
    "            return n\n",
    "        if n==1:\n",
    "           return  1\n",
    "        \n",
    "        char_dict = self.helper(s)\n",
    "        \n",
    "        return(self.longestSubstring_helper(s,0,n-1,k,char_dict))\n",
    "       \n",
    "\n",
    "        \n",
    "    def longestSubstring_helper(self,s,begin,end,k,char_dict):\n",
    "        if end<begin:\n",
    "            return 0\n",
    "        # 边界讨论\n",
    "        if k>(end-begin+1):\n",
    "            return 0\n",
    "        if k ==1 :\n",
    "            return (end-begin+1)\n",
    "        if end==begin:\n",
    "           return  1\n",
    "        \n",
    "        for i in range(begin,end+1):\n",
    "            if i ==0:\n",
    "                char_dict[str(begin)+\"_\"+str(end)] =char_dict[str(0)+\"_\"+str(end)]\n",
    "            else:\n",
    "                char_dict[str(begin)+\"_\"+str(end)] = \\\n",
    "                dict(Counter(char_dict[str(0)+\"_\"+str(end)])-Counter(char_dict[str(0)+\"_\"+str(begin-1)]))\n",
    "            \n",
    "            print(char_dict[str(begin)+\"_\"+str(end)])\n",
    "            if char_dict[str(begin)+\"_\"+str(end)][s[i]]<k:\n",
    "                return max(self.longestSubstring_helper(s,begin,i-1,k,char_dict),\\\n",
    "                self.longestSubstring_helper(s,i+1,end,k,char_dict))\n",
    "\n",
    "            else :\n",
    "                pass\n",
    "        return end-begin+1\n",
    "            \n",
    "                        \n",
    "       \n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "       \n",
    "\n",
    " # 函数目标 通过o(n)次的计算获取s中每个s[0:i]之间字符出现的次数\n",
    " # 应用时 根据s[0:end]的字典 - s[0:begin-1]的字典，获取s[begin:end]的字典个数\n",
    "    def helper(self,s:str):\n",
    "        n =  len(s)\n",
    "        char_dict = defaultdict(lambda : defaultdict(int))\n",
    "        for i in range(n): \n",
    "            if i==0:           \n",
    "                char_dict[str(0)+\"_\"+str(i)][s[i]]=1\n",
    "            else:\n",
    "                char_dict[str(0)+\"_\"+str(i)] =char_dict[str(0)+\"_\"+str(i-1)].copy()\n",
    "                \n",
    "                char_dict[str(0)+\"_\"+str(i)][s[i]]+=1\n",
    "        return char_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieCount:\n",
    "    def __init__(self):\n",
    "        self.dct = dict()\n",
    "        return\n",
    "\n",
    "    def update(self, cnt, i):\n",
    "        # 更新单词与前缀计数\n",
    "        cur = self.dct\n",
    "        for w in cnt:\n",
    "            if w not in cur:\n",
    "                cur[w] = dict()\n",
    "            cur = cur[w]\n",
    "        cur[\"ind\"] = i\n",
    "        return\n",
    "\n",
    "    def query(self, word, k):\n",
    "        # 查询前缀单词个数\n",
    "        n = len(word)\n",
    "        res = -2\n",
    "        \n",
    "        def dfs(cur, i):\n",
    "            nonlocal res\n",
    "            if i == n:\n",
    "                if res == -2 or res > cur[\"ind\"]:\n",
    "                    res = cur[\"ind\"]\n",
    "                return \n",
    "            for w in cur:\n",
    "                if w <= word[i]-k or word[i] == w:\n",
    "                    dfs(cur[w], i+1)\n",
    "            return \n",
    "        \n",
    "        dfs(self.dct, 0)\n",
    "        return res\n",
    "    \n",
    "    \n",
    "    \n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        cnt = [0]*26\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        trie = TrieCount()\n",
    "        trie.update(cnt[:], -1)\n",
    "        for i in range(n):\n",
    "            cnt[ord(s[i])-ord(\"a\")] += 1\n",
    "            j = trie.query(cnt[:], k)\n",
    "            if j != -2:\n",
    "                ans = ans if i-j < ans else i-j\n",
    "            trie.update(cnt[:], i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 50\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        # 前缀和\n",
    "        prefix = [[0] * (n+1) for _ in range(26)]\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(26):\n",
    "                prefix[j][i] = prefix[j][i-1]\n",
    "            index = ord(s[i-1]) - ord(\"a\")\n",
    "            prefix[index][i] += 1\n",
    "        print(np.array(prefix))\n",
    "\n",
    "\n",
    "        def helper(start, end):\n",
    "            for i in range(start, end+1):\n",
    "                # 找到中断点\n",
    "                index = ord(s[i]) - ord(\"a\")\n",
    "                if prefix[index][end+1] - prefix[index][start] < k:\n",
    "                    return max(helper(start, i - 1), helper(i + 1, end))\n",
    "            \n",
    "            return max(end - start + 1, 0)\n",
    "\n",
    "        return helper(0, n - 1) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subtract_list(self, list1, list2):\n",
    "        new_list = []\n",
    "        \n",
    "        for i in range(len(list1)):\n",
    "            new_list.append(list1[i] - list2[i])\n",
    "        \n",
    "        return new_list\n",
    "    \n",
    "    def count_longest(self, s, begin, end, k):\n",
    "        count = self.subtract_list(self.dp[end], self.dp[begin - 1]) if begin > 0 else self.dp[end]\n",
    "        \n",
    "        for i in range(begin, end + 1):\n",
    "            if count[ord(s[i]) - ord('a')] < k:\n",
    "                return max(self.count_longest(s, begin, i - 1, k), self.count_longest(s, i + 1, end, k))\n",
    "        \n",
    "        return end + 1 - begin\n",
    "        \n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        if len(s) == 0 or len(s) < k:\n",
    "            return 0\n",
    "        \n",
    "        self.dp = []\n",
    "        \n",
    "        for c in s:\n",
    "            if len(self.dp) == 0:\n",
    "                curr_dp = [0] * 26\n",
    "            else:\n",
    "                curr_dp = self.dp[-1][:]\n",
    "            curr_dp[ord(c) - ord('a')] += 1\n",
    "            self.dp.append(curr_dp)\n",
    "        \n",
    "        return self.count_longest(s, 0, len(s) - 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        def helper(i, j):\n",
    "            nonlocal res\n",
    "            dic = {}\n",
    "            for ind in range(i, j + 1):\n",
    "                char = s[ind]\n",
    "                if char in dic.keys():\n",
    "                    dic[char][0] += 1\n",
    "                else:\n",
    "                    dic[char] = [1, ind]\n",
    "            succeed = True\n",
    "            for char, li in dic.items():\n",
    "                if li[0] < k:\n",
    "                    helper(i, li[1] - 1)\n",
    "                    helper(li[1] + 1, j)\n",
    "                    succeed = False\n",
    "                    break\n",
    "            if succeed and j - i + 1 > res:\n",
    "                res = j - i + 1\n",
    "        helper(0, n - 1)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\r\n",
    "        for i in range(len(s)):\r\n",
    "            if s.count(s[i])<k:\r\n",
    "                return max(self.longestSubstring(s[:i],k),self.longestSubstring(s[i+1:],k))\r\n",
    "        return len(s)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        flag = True\n",
    "        if len(s) == 0:\n",
    "            return 0\n",
    "        for i in range(len(s)):\n",
    "            if s.count(s[i]) < k:\n",
    "                flag = False\n",
    "                break\n",
    "        if flag == True:\n",
    "            return len(s)\n",
    "        left = s[:i]\n",
    "        right = s[i+1:]\n",
    "        return max(self.longestSubstring(left,k), self.longestSubstring(right,k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        for i in range(len(s)):\n",
    "            if s.count(s[i])<k:\n",
    "                return max(self.longestSubstring(s[:i],k),self.longestSubstring(s[i+1:],k))\n",
    "        return len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        record=0\n",
    "        for i in s:\n",
    "            if s.count(i)<k:\n",
    "                record=1\n",
    "                return max(self.longestSubstring(s[:s.index(i)],k),self.longestSubstring(s[s.index(i)+1:],k))\n",
    "        if record==0:\n",
    "            return len(s)\n",
    "  \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        for i, c in enumerate(s):\n",
    "            if s.count(c)<k:\n",
    "                left = self.longestSubstring(s[:i],k)\n",
    "                right = self.longestSubstring(s[i+1:],k)\n",
    "                return max(left, right)\n",
    "        return len(s)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        if len(s) < k:\n",
    "            return 0\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if s.count(s[i]) < k:\n",
    "                return max( self.longestSubstring(s[:i], k), self.longestSubstring(s[i+1:], k) )\n",
    "\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        # 分治：对于一个字符串来说，如果要求子串最少出现k次，\n",
    "        # 那么如果某些字母出现的次数小于k,\n",
    "        # 这些字母一定不会出现在最长的子串中，并且这些字母将整个字符子串分割成小段，\n",
    "        # 这些小段有可能是最长的\n",
    "        # 但是由于被分割了，还是要检查这一小段，\n",
    "        # 如果某些字母出现的次数小于k,会将小段继续分割下去,\n",
    "        # 比如字符串\"aacbbbdc\"，要求最少出现2次,我们记录左右闭区间，，\n",
    "        # 第一轮[0,7]，处理\"aacbbbdc\"，d只出现了一次不满足，\n",
    "        # 于是递归解决区间[0,5]、[7,7]\n",
    "        # 第二轮[0,5]，处理\"aacbbb\"，  c只出现了一次不满足，\n",
    "        # 于是递归解决区间[0,1]、[3,4] \n",
    "        # 第二轮[7,7]，处理\"c\"，       c只出现了一次不满足，不继续递归\n",
    "        # 第三轮[0,1]，处理\"aa\"，      满足出现次数>=2,ret=2\n",
    "        # 第三轮[3,4]，处理\"bbb\"，     满足出现次数>=2 ret=3;\n",
    "        l = [0 for _ in range(26)]   # 分别表示a-z的字母\n",
    "        for c in s:\n",
    "            l[ord(c) - 97] += 1\n",
    "        i = 0\n",
    "        while i < len(s) and l[ord(s[i]) - 97] >= k:\n",
    "            i += 1\n",
    "        if i == len(s):\n",
    "            return len(s)\n",
    "        # 字符i出现的次数小于k，那么整个s字符串就被s[i]分割了\n",
    "        l = self.longestSubstring(s[: i], k)\n",
    "        r = self.longestSubstring(s[i + 1: ], k)\n",
    "        return max(l, r)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        if len(s) < k:\n",
    "            return 0\n",
    "        \n",
    "        for i in range(len(s)):\n",
    "            if s.count(s[i]) < k:\n",
    "                return max(self.longestSubstring(s[:i],k),self.longestSubstring(s[i+1:],k))\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        if len(s) < k:\n",
    "            return 0\n",
    "        # for char in set(s):\n",
    "        #     if s.count(char) < k:\n",
    "                # return max(self.longestSubstring(t,k) for t in s.split(char))\n",
    "        for i,char in enumerate(s):\n",
    "            if s.count(char) <k:\n",
    "                return max(self.longestSubstring(s[:i],k),self.longestSubstring(s[i+1:],k))\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        if len(s) < k:\n",
    "            return 0\n",
    "        # for char in set(s):\n",
    "        #     if s.count(char) < k:\n",
    "        #         return max(self.longestSubstring(t,k) for t in s.split(char))\n",
    "        for i,char in enumerate(s):\n",
    "            if s.count(char) <k:\n",
    "                return max(self.longestSubstring(s[:i],k),self.longestSubstring(s[i+1:],k))\n",
    "        return len(s)\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\n",
    "        def dp(s):\n",
    "            for i,e in enumerate(s):\n",
    "                if s.count(e) < k:\n",
    "                    return max(dp(s[:i]),dp(s[i+1:]))\n",
    "            return len(s)\n",
    "        return dp(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestSubstring(self, s: str, k: int) -> int:\r\n",
    "        return dfs(s, k)\r\n",
    "\r\n",
    "\r\n",
    "def dfs(s, k):\r\n",
    "    n = len(s)\r\n",
    "    # 字符串长度不超过k  那么这个字符串肯定不是  返回0\r\n",
    "    if n < k:\r\n",
    "        return 0\r\n",
    "    # 如果这个字符串里字符都超过k次 返回字符串长度\r\n",
    "    if isVaild(s, k):\r\n",
    "        return n\r\n",
    "    for i, val in enumerate(s):\r\n",
    "        # 如果这个值 在s里没超过k次  那么包含这个字符的字符串就一定不满足要求\r\n",
    "        if s.count(val) < k:\r\n",
    "            # 所以左右分开递归\r\n",
    "            return max(dfs(s[0:i], k), dfs(s[i + 1 :], k))\r\n",
    "\r\n",
    "# 判断这个字符串是否满足出现次数都超过k\r\n",
    "def isVaild(s, k):\r\n",
    "    # 字符串长度不超过k  那么这个字符串肯定不是  返回false\r\n",
    "    if len(s) <k :\r\n",
    "        return False\r\n",
    "    # 一个一个加字典里\r\n",
    "    for val in s:\r\n",
    "        # 如果某个字符不超过k次  直接false\r\n",
    "        if s.count(val)<k:\r\n",
    "            return False\r\n",
    "    return True\r\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
